package com.darrenchan.leetcode;

import java.util.Arrays;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-25 21:51
 */
public class Q215 {
    public int findKthLargest(int[] nums, int k) {
        return select(nums, 0, nums.length - 1, k - 1);
    }

    private int select(int[] nums, int start, int end, int k) {
        if(start >= end) {
            return nums[k];
        }

        int i = start, j = end;
        int pivot = nums[(i + j) / 2];
        while(i <= j) {
            while(i <= j && nums[i] > pivot) {
                i++;
            }

            while(i <= j && nums[j] < pivot) {
                j--;
            }

            if(i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;

                i++;
                j--;
            }
        }

        if(k <= j) {
            return select(nums, start, j, k);
        }

        if(k >= i) {
            return select(nums, i, end, k);
        }

        return nums[k];
    }

}
